package com.base.listNode;

/**
 * 725. 分隔链表
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 * <p>
 * 每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 * <p>
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 * <p>
 * 返回一个由上述 k 部分组成的数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年09月22日 20:28
 */
public class SplitListToParts {


    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode rear = head;
        // 链表的长度
        int n = 0;
        while (rear != null) {
            n++;
            rear = rear.next;
        }

        int p = n / k, q = n % k;

        ListNode[] ret = new ListNode[k];
        for (int i = 0; i < k; i++) {
            if (head == null) {
                ret[i] = null;
                continue;
            }
            ListNode cur = head;
            ret[i] = cur;
            int tmp = q > 0 ? p + 1 : p;
            q--;
            while (tmp > 1 && cur.next != null) {
                cur = cur.next;
                tmp--;
            }

            head = cur.next != null ? cur.next : null;
            cur.next = null;

        }
        return ret;

    }
}
